package com.yvon.service.demo.algorithm.offer;

/**
 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 */
public class P39 {


    /**
     * https://www.zhihu.com/question/49973163
     */
    class Solution {
        private int majorityElement(int[] nums) {
            int major = 0;
            int count = 0;

            for (int i = 0; i < nums.length; i++) {
                if (major == nums[i]) {
                    count ++;
                } else if (--count == 0) {
                    major = nums[i];
                    count = 1;
                }
            }
            return major;
        }
    }
}
